//
//  543. 二叉树的直径.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/9/14.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution543 {
    var result = 0
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        deep(root)
        return result - 1
    }
    @discardableResult
    func deep(_ root: TreeNode?) -> Int {
        guard let node = root else {
            return 0
        }
        let leftDep = deep(node.left)
        let rightDep = deep(node.right)
        let depth = max(leftDep, rightDep) + 1
        result = max(result, leftDep + rightDep + 1)
        return depth
    }
   
    static func test() {
        let solution = Solution543()
        let node1 = TreeNode(1)
        let node2 = TreeNode(2)
        let node3 = TreeNode(3)
        let node4 = TreeNode(4)
        let node5 =  TreeNode(5)
        
        node1.left = node2
        node1.right = node3
        node2.left = node4
        node2.right = node5
        
        let result = solution.diameterOfBinaryTree(node1)
        print(result)
    }
}
